package LinkedList;

/**
 *  题目 ：删除链表的倒数第N个节点
 *  题目详细描述 ：
 *  给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 */
public class P19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        /**
         * 思路 ：
         * 双指针，即通过一个指针先移动n步，然后双指针容易相同速度进行移动，从而得到倒数第n个节点；
         * 同时，由于需要删除倒数第n个节点，即我们需要得到倒数第n+1个节点；（通过prev指针，在链表遍历的过程中进行获取）
         * 注意 ：
         *      特殊情况：若是删除的是链表的头节点话，返回的值就不是head节点，而是prev.next节点；
         *      需要引入一个符号变量flag（Boolean类型），用来判断是否删除的是头节点；
         */
        ListNode node1 = head;
        ListNode node2 = head;
        Boolean flag = true;
        ListNode prev = new ListNode(0);
        prev.next = head;
        for (int i = 0; i < n; i++) {
            node1 = node1.next;
        }
        // 若是进入此循环的话，即我们所删除的不是头节点；
        while(node1 != null){
            flag = false;
            node1 = node1.next;
            prev = node2;
            node2 = node2.next;
        }
        prev.next = node2.next;
        // 若是删除的是头节点的话，即需要取返回prev.next节点
        if(flag){
            return prev.next;
        }
        return head;
    }
}
